package ljl.alg.wangzheng_camp.round1.sort;

import commons.ListNode;

/**
 * 做错了
 *
 * 感觉好难好难的
 *
 */
public class _147_insertion_sort_list {
    
    /**
     * [4,2,1,3]
     *
     *
     */
    public ListNode insertionSortList2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0, head);
        ListNode p = head;
        while (p.next != null) {
            ListNode next = p.next;
            // 否则找地方插入 next，
            // p.next = next.next，p = p.next
            
            /*
            * 其实不难，就是这个地方，由于插入了，p 不该往后走
            * 走就错
            * */
            if (next.val < p.val) {
                // 断开 next，然后插入
                p.next = next.next;
                insert(dummy, next);
            } else {
                p = p.next;
            }
        }
        return dummy.next;
    }
    void insert(ListNode dummyHead, ListNode node) {
        while (dummyHead.next != null && dummyHead.next.val <= node.val) {
            dummyHead = dummyHead.next;
        }
        node.next = dummyHead.next;
        dummyHead.next = node;
    }
    
    /**
     * 他写的和我几乎一样，我试试它的写法
     * */
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0, head);
        ListNode prev = head, cur = head.next;
        while (cur != null) {
            if (prev.val <= cur.val) {
                prev = cur;
            } else {
                prev.next = cur.next;
                ListNode p = dummy;
                while (p.next.val <= cur.val)
                    p = p.next;
                cur.next = p.next;
                p.next = cur;
            }
//            这错写成 cur = cur.next 了。cur 可能会被插入的，这么写肯定不对
//            应该是 cur = prev.next
            cur = prev.next;
        }
        return dummy.next;
    }
}
